#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

int minDepth(TreeNode *root) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    if(!root)
        return 0;

    if(!root->left && !root->right)
        return 1;

    int leftDepth = 0x7FFFFFFF;
    if(root->left)
        leftDepth = minDepth(root->left);
    int rightDepth = 0x7FFFFFFF;
    if(root->right)
        rightDepth = minDepth(root->right);
    return leftDepth > rightDepth ? (rightDepth+1) : (leftDepth+1);
}   

int main(){
    return 0;
}